#include<iostream>
#include<stack>
using namespace std;

typedef struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}TreeNode;

class Solution {
public:
	bool Find(TreeNode* root, TreeNode* x)
	{
		if (root == nullptr)
			return false;
		if (root == x)
			return true;
		return Find(root->left, x) || Find(root->right, x);
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
	{
		if (p == root)
			return p;

		if (q == root)
			return q;

		stack<TreeNode*> stp;
		stack<TreeNode*> stq;

		TreeNode* curp = root;
		while (curp != p)
		{
			stp.push(curp);
			if (Find(curp->left, p))
			{
				curp = curp->left;
			}
			else if (Find(curp->right, p))
			{
				curp = curp->right;
			}
		}

		TreeNode* curq = root;
		while (curq != q)
		{
			stq.push(curq);
			if (Find(curq->left, q))
			{
				curq = curq->left;
			}
			else if (Find(curq->right, q))
			{
				curq = curq->right;
			}
		}

		while (stq.size() != stp.size())
		{
			if (stq.size() > stp.size())
			{
				stq.pop();
			}
			else if (stq.size() < stp.size())
			{
				stp.pop();
			}
			else
			{
				break;
			}
		}

		while (stq.top() != stp.top())
		{
			stq.pop();
			stp.pop();
		}

		return stp.top();
	}
};